package com.lun.swordtowardoffer2.c08;

import com.lun.util.BinaryTree.TreeNode;

public class MaxPathSum {

	public int maxPathSum(TreeNode node) {
		int[] maxSum = {Integer.MIN_VALUE};
		dfs(node, maxSum);
		return maxSum[0];
	}

	private int dfs(TreeNode node, int[] maxSum) {
		if(node == null)
			return 0;
		
		int[] maxLeftSum = {Integer.MIN_VALUE};
		int left = Math.max(0, dfs(node.left, maxLeftSum));//0表示如果递归分支得出负数，干脆不要分支了
		
		int[] maxRightSum = {Integer.MIN_VALUE};
		int right = Math.max(0, dfs(node.right, maxRightSum));
		
		maxSum[0] = Math.max(maxLeftSum[0], maxRightSum[0]);
		maxSum[0] = Math.max(maxSum[0], node.val + left + right);
		
		return node.val + Math.max(left, right);
	}
	
}
